__author__ = 'st316'
'''
Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2.
(each operation is counted as 1 step.)

You have the following 3 operations permitted on a word:

a) Insert a character
b) Delete a character
c) Replace a character
'''


class Solution:
    # @return an integer
    def minDistance(self, word1, word2):
        d = [[0 for j in xrange(len(word2) + 1)] for i in xrange(len(word1) + 1)]
        for i in xrange(len(word2) + 1):
            d[0][i] = i
        for i in xrange(len(word1) + 1):
            d[i][0] = i
        for i in xrange(1, len(word1) + 1):
            for j in xrange(1, len(word2) + 1):
                d[i][j] = min(d[i - 1][j] + 1, d[i][j - 1] + 1,
                              d[i - 1][j - 1] if word1[i - 1] == word2[j - 1] else d[i - 1][j - 1] + 1)
        return d[len(word1)][len(word2)]


if __name__ == '__main__':
    s = Solution()
    print s.minDistance('adb', 'aaa')
